package com.hdu.other.dp.shuweiDp;

import javax.print.attribute.standard.MediaSize;

public class lc600 {
    class Solution {
        public int findIntegers(int n) {
            int[] cnt = new int[32];
            cnt[0] = 1;
            cnt[1] = 2;
            for (int i = 2; i < 32; i++) {
                cnt[i] = cnt[i - 1] + cnt[i - 2];
            }
            return f(cnt, 30, n);
        }

        int f(int[] cnt, int i, int n) {
            if (i == -1) {
                return 1;
            }
            int ans = 0;
            if ((n & (1 << i)) != 0) {
                ans += cnt[i];
                if ((n & (1 << (i + 1))) != 0) {
                    return ans;
                }
            }
            ans += f(cnt, i - 1, n);
            return ans;
        }
    }
}
